/*
 * @lc app=leetcode.cn id=30 lang=javascript
 *
 * [30] 串联所有单词的子串
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function (s, words) {
  const n = s.length;
  const wordCnt = words.length;
  const wordLen = words[0].length;
  const totalLen = wordLen * words.length;

  const wordMap = new Map();

  // 构建词汇数目表
  for (const w of words) {
    wordMap.set(w, (wordMap.get(w) || 0) + 1);
  }

  const res = [];

  // 从头开始逐单词匹配, 需要注意等号
  for (let i = 0; i <= n - totalLen; i++) {
    const seenMap = new Map();
    let matched = true;
    for (let j = 0; j < wordCnt; j++) {
      const start = i + j * wordLen;
      const word = s.substring(start, start + wordLen);
      if (!wordMap.has(word)) {
        matched = false;
        break;
      }

      const cnt = (seenMap.get(word) || 0) + 1;

      if (wordMap.get(word) < cnt) {
        matched = false;
        break;
      }

      seenMap.set(word, cnt);
    }

    if (matched) res.push(i);
  }
  return res;
};
// @lc code=end
